iT邦幫忙

2022 iThome 鐵人賽
DAY 29
0
Software Development

與作業系統的第一類接觸 : 探索 xv6系列 第 29 篇

Day-28 Pointer, A Pointer of A Pointer, Function Pointer

14th鐵人賽 c 作業系統 xv6 自學筆記
3896 瀏覽

  • 分享至 

  • xImage
    •  

前言

在 xv6 中，我們可以看到各種 C 語言的指標操作，而在這一篇章中，我們將回顧一些指標的概念，並且結合部分 xv6 的程式碼進行更多的理解。

指向陣列的指標 (pointer to array)

int v[5] = { 1,2,3,4,5 };
int *v_ptr = v;

v 是一個陣列型別的變數，型別為 int (*)[5]
v_ptr 為指向陣列第一個元素的指標，陣列第一個元素為 int，因此v_ptr的型別為 int

陣列型別:
陣列內元素型別 (*變數名稱)[陣列大小];

如果我們希望一個指標不要只是指向陣列第一個元素，而是指向整個陣列，我們需要使用下面方式來宣告指向陣列的指標

假設以下為一個指向含有五個元素的整數陣列的指標

int v[5] = { 1,2,3,4,5 };
int (*v_ptr)[5] = &v;

注意第二行，如果我們只寫 v，我們取得的是指向 v 陣列第一個元素，型別為 int *。必須使用 &v 才會得到 int (*v)[5] 陣列的型別。

我們可以使用指標偏移驗證看看

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int v[5] = { 1,2,3,4,5 };
    int *v_ptr = v;
    int (*v_array_ptr)[5] = &v;
    
    printf("v_ptr : %p\n", v_ptr);
    printf("v_ptr + 1 : %p\n", v_ptr + 1);
    printf("v_array_ptr : %p\n", v_array_ptr);
    printf("v_array_ptr + 1 : %p\n", v_array_ptr + 1);
}

輸出

v_ptr : 0061FF04
v_ptr + 1 : 0061FF08
v_array_ptr : 0061FF04
v_array_ptr + 1 : 0061FF18

可以看到 v_ptr 偏移一個單位為 4 bytes，這是因為 v_ptr 指向的型別為 int，一個 int 為 4 bytes，因此一次偏移 4 bytes。
v_array_ptr 偏移一次單位為 20 bytes，這是因為 v_array_ptr 指向的型別為 int (*)[5]，一個有 5 個 int 大小的陣列為 20 bytes，因此一次偏移 20 bytes (注意，這裡是 16 進位表示，因此 18 - 4 為 10 進位的 20)

我們可以使用這兩種指標對陣列進行遍歷

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int v[5] = { 1,2,3,4,5 };
    int *v_ptr = v;
    int (*v_array_ptr)[5] = &v;
    
    for(int i = 0; i < 5; i++)
    {
        printf("%d ", *(v + i));
    }
    printf("\n");
    for(int i = 0; i < 5; i++)
    {
        printf("%d ", (*v_array_ptr)[i]);
    }
}

輸出

1 2 3 4 5
1 2 3 4 5

指標的指標 (A Pointer of A Pointer)

指標的指標，為一個指標變數，指向的型別為指標型別，以下範例

int a = 10;
int *ptr_1 = &a;
int **ptr_2 = &ptr_1;

printf("a = \t%d\n", a);
printf("*ptr_1 = \t%d\n", *ptr_1);    
printf("**ptr_2 = \t%d\n", **ptr_2);

輸出

a = 10
*ptr_1 = 10
**ptr_2 = 10

說明
宣告 a 為一個 int 變數 初始化為 10
宣告 ptr_1 為一個指標變數 指向 int 型別的資料
宣告 ptr_2 為一個指標變數 指向 int * 型別的資料 直觀上來說 我們可能直接寫成

int* *ptr_2 = &ptr_1;

但是習慣上會寫成

int **ptr_2 = &ptr_1;

而輸出結果:
*ptr_1，*ptr_1 中存放的為 a 的記憶體地址，對其反參考，即為 a 的值，也就是 10

**ptr_2,**ptr_2 為一個指向 int * 型別的指標，*ptr_1 的型別為 int *，因此
**ptr_2 中為 *ptr_1 的記憶體地址，對其進行反參考，也就是對*ptr_1 進行反參考，即為 a = 10

注意
在宣告一個變數為指標變數時 會在其變數名稱加上"*" 如int *ptr_1
所以，別把第三行最外面的"*"和第七行最外面的"*"混淆了!!第七行正確的解讀應該為
*(*ptr_2)，也就是對*ptr_2進行反參考。

指標的指標 (A Pointer of A Pointer) 與二維陣列

int num[3][4];

==C 語言在看二維陣列時，會將它視為一個一維陣列，每個一維陣列的元素為一維陣列。(這件事情很重要)==

  1. 這是一個二維陣列，由三個一維陣列組合而成，每一個一維陣列中含有 4 個 int。
  2. num[0]、num[1] 與 num[2] 為整數指標常數 int * const，
    它們分別指向這 3 個一維陣列開頭第一個元素
  3. num 是含有 3 個元素的陣列，每個元素是 4 個整數的陣列，
    num 或是 &num[0] 是第一個元素的記憶體位址。

解讀:

  1. 陣列名稱 num 為一個指標常數 ( int ** const )，指向型別指標的指標 (pointer to pointer)
  2. num[0] 到 num[2] 也是指標常數 (int * const)，指向型別為指標，指向每一個一維陣列中第一個元素。
  3. num[0][0] 為整數 (int)

我們可以思考二維陣列和一維陣列之間的關係

int array_1[5];
int array_2[2][5];

在這個例子中，我們可以說 array_1 為指標指向 array_1[0]，==但我們不能說 array_2 為指標指向 array_2[0][0]==，printf 出來結果雖然一樣，但兩者的意義截然不同。array_1 做為指向 int * 型別的指標，而 array_2 為做為指向 int ** 型別的指標。
根據上面這些規則，我們可以得到一件事情

int main(void) {
  int num[3][4];
  int counter = 0;
  
  printf("num = %p\n", num);
  printf("num[0] = %p\n", num[0]);
  printf("num[0][0] = %p\n", &num[0][0]); 
}

Output:
num = 0x7ffcf767c270
num[0] = 0x7ffcf767c270
num[0][0] = 0x7ffcf767c270

num 指向 num[0]，而 num[0]指向 num[0][0]，因此記憶體地址皆相同，==差別只在三者的資料型別不同==

我們可以運用指標的指標去遍歷二維陣列

int main(void)
{
    int num[3][2] = {{2,3},{1,4},{5,6}}; 
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            printf("%d", *(num[i] + j));
        }
    }
}

i 每一次 + 1，表示從 num[i] 移動到 num[i + 1]，而 j 每一次移動 num[i] 所指向的型別，指向的型別為 int，因此每一次移動 4 bytes。

int main(void)
{
    int num[3][2] = {{2,3},{1,4},{5,6}}; 
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            printf("%d", *(*(num + i) + j));
        }
    }
}

一層一層進行解讀:

num + i，num 的型別為 int **，為一個指標指向一個一維陣列，代表 num[0] 和 num[0][0] 的記憶體地址，移動 i，表示一次移動一個一維陣列的大小，因為指標的偏移量是看指標所指向的對象而決定，像是 int *，指向 int，所以一次移動 4 bytes。num 指向的是一個一維陣列，一個一維陣列在這裡大小為 4 * 2 bytes，因此，num + i 的意義為一次移動一列

而對 num + i 進行反參考，可以這樣思考，我們對 int * 進行反參考就是得到 int，指向整數的指標反參考得到整數，而 int ** 進行反參考即得到 int *。

現在思考以下
*(num + i) + j，*(num + i) 的型別為 int *，指向的是 int，意義上就是指向陣列中的元素，因此，一次偏移 j，就是一次偏移一個 int 的量，也就是 4 bytes。也就是每一次偏移 j 我們就可以得到每一列元素的數值。

而我們在對 *(num + i) + j 進行反參考，也就是對 int * 進行反參考，得到的即為 int，也就是陣列中元素的型別，如此，我們就可以通過 *(*(array_2d + i) + j) 來得到陣列中所有元素了。

注意，二維陣列使用malloc進行宣告

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int **a = malloc(sizeof(int*) * 4);
    for(int i = 0; i < 4; i++)
    {
        a[i] = malloc(sizeof(int) * 2);
    }
}

這裡，使用了 malloc 宣告一個二維矩陣，我們可以注意一下他的記憶體分布

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int **a = malloc(sizeof(int*) * 3);
    for(int i = 0; i < 4; i++)
    {
        a[i] = malloc(sizeof(int) * 2);
    }
    printf("a[0][0] = %d\n", &a[0][0]);
    printf("a[0][1] = %d\n", &a[0][1]);
    printf("a[1][0] = %d\n", &a[1][0]);
    printf("a[2][0] = %d\n", &a[2][0]);
}

輸出

a[0][0] = 13440632
a[0][1] = 13440636
a[1][0] = 13440648
a[2][0] = 13440664

我們可以發現到，事實上我們二維陣列中，每一個一維陣列只佔 8 bytes，但是 a[0] 和 a[1] 卻相差了 14 bytes，a[1] 和 a[2] 相差了 16 bytes，這裡我們只要知道一件事情，使用 malloc() 分布記憶體，==並不保證多維陣列記憶體分布的連續性，因此使用指標位移的操作需要格外注意。==

Function Pointer

在 xv6 中，我們可以看到以下程式碼，位於 file.h

struct devsw {
  int (*read)(int, uint64, int);
  int (*write)(int, uint64, int);
};

extern struct devsw devsw[];

#define CONSOLE 1

在 xv6 中我們可以想像周遭有許多 I/O 設備，而這一些設備都會有對應的 write() 和 read()，而我們使用了 devsw 這個 struct 來儲存，我們可以觀察這個 struct 中的 member，可以發現他們都是 function pointer，以 read 來說，他為一個 function pointer，指向參數 (parameter) 為 int, uint64，且回傳值為 int 的 function，而我們接著看到 console.c 中

int
consoleread(int user_dst, uint64 dst, int n)
...
int
consolewrite(int user_src, uint64 src, int n)
...
devsw[CONSOLE].read = consoleread;
devsw[CONSOLE].write = consolewrite;

可以看到我們使用 devsw 這個結構中的成員去存放 consoleread() 這個 function 的記憶體地址，在經過這邊的操作，我們的 devsw[CONSOLE] 的 member，read 和 write 就會指向到 consoleread() 和 consolewrite() 這兩個 function。

我們下面可以進行一個簡單的 function pointer 實驗

#include <stdio.h>

void func(void);
int main(void)
{
    void (*funcPtr)(void) = func;
    printf("Address of funcPtr :%X\n", &funcPtr);
    printf("Context of funcPtr :%X\n", funcPtr);
    printf("Dereference of funcPtr :%X\n", *(funcPtr));
    printf("\n");
    printf("Address of func :%X\n", &func);
    printf("Context of func :%X\n", func);
    printf("Dereference of func :%X\n", (*func));
    printf("\n");
    funcPtr();
    (*funcPtr)();
}

void func(void)
{
    printf("Call func\n");
}

output

Address of funcPtr :61FF1C
Context of funcPtr :401519    
Dereference of funcPtr :401519

Address of func :401519       
Context of func :401519       
Dereference of func :401519   

Call func
Call func

說明:
我們這邊宣告了一個指向參數為 void，回傳值為 void 的 function pointer，名稱為 funcPtr，funcPtr 指向到 func，也就是 funcPtr 裡面存放的是 func 所在的位置，從我們的輸出可以看到 funcPtr 的內容就是 func 所在的記憶體地址。

我們看到我們輸出了 6 個記憶體地址，以下解釋

  1. 第一個記憶體地址為 funcPtr 這個 function pointer 所在的記憶體地址。
  2. 第二個為 funcPtr 裡面儲存的內容，裡面儲存的內容為 func，這裡可以發現，其實函式名稱代表的就是函式的記憶體地址，所以這邊印出來的，就是 func 的記憶體地址，為 funcPtr 的內容。
  3. 第三個為對 funcPtr 內容的反參考，也就是對 funcPtr 指向的記憶體地址進行反參考，funcPtr 的內容為 func 的記憶體地址，而對他進行反參考，也就是取得 func 的記憶體指向的內容，func 指向的記憶體內容就是 func 在記憶體中的位置，因此對他進行反參考依然是 func 的記憶體地址。

而上面的概念延伸下來，下面的呼叫行為就可以理解了，funcPtr() 就是使用 () 內的引數作為 func() 的參數進行函式呼叫。而 (*funcPtr)()，就是反參考 funcPtr，而上面說過反參考依然為 func() 的記憶體地址，因此效果相同

同理，我們將這樣的概念往下推演，可以得到下面兩種函式指標的 define 是相同的

#include <stdio.h>

void func(void);
int main(void)
{
    void (*funcPtr)(void) = func;
    void (*funcPtr1)(void) = *func;
    void (*funcPtr2)(void) = &func;
    funcPtr();
    funcPtr1();
    funcPtr2();
}

void func(void)
{
    printf("Call func\n");
}

output

Call func
Call func
Call func

而我們在看回 xv6 的程式碼片段，我們就能夠直觀的明白了

devsw[CONSOLE].read = consoleread

而我們之後如果要呼叫 CONSOLE 對應的 read，可以使用以下

 if(f->type == FD_PIPE){
    r = piperead(f->pipe, addr, n);
  } else if(f->type == FD_DEVICE){
    if(f->major < 0 || f->major >= NDEV || !devsw[f->major].read)
      return -1;
    r = devsw[f->major].read(1, addr, n);

看起來就像是呼叫 CONSOLE 物件的方法，讓 C 有了物件導向的概念。

main() 指令參數

main函數的原型為以下宣告:

int main(int argc, char * argv[])
{
    
}

argc 為指令的個數，最小值為 1 (因為至少含有程式執行的名稱)，argv 的解讀，可以先解讀成為 argv 為一個指標陣列，指向的元素型別為 char。其實這個意思等價於 argv 為一個指標變數，指向型別為 char * ，那為什麼不將 char * argv[] 設計成 char ** argv 呢? 原因為告訴程式設計師 argv 它不單單是一個指標，而是指向一個指標陣列的第一個元素，每個元素型別為 char * ，指向指令的第一個字串。

#include <stdio.h>
int main(int argc, char *argv[])
{
    printf("argc = %d\n", argc);
    for(int i = 0; i < argc; i++)
    {
        printf("argv[%d]=%s\n", i, argv[i]);
    }
    return 0;
}

Output:
$ gcc main.c
$ ./a.out a b c
argc = 4
argv[0]=./a.out
argv[1]=a
argv[2]=b
argv[3]=c

其實也可以將 for 的中止條件改寫為 for(i=0; argv[i] != NULL; i++)

而這裡我們可結合前面的記憶體分部一起看，arg 的部分會位於記憶體中以下位置

< Process memory layout >

指向結構的指標 (Pointer to struct)

下面，我們宣告一個指標變數 new_node，指向型別為 Node

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int x;
    int y;
}Node;

int main(void)
{
    Node* new_node;
}

而我們要如何對結構的成員進行初始化呢? 如果我們是使用結構變數宣告結構，我們可以使用 . 運算子存取每一個結構，而如果使用指標宣告結構，則我們需要使用 -> 運算子來存取結構

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int x;
    int y;
}Node;

int main(void)
{
    Node* new_node = malloc(sizeof(Node) * 1);
    new_node->x = 2;
    new_node->y = 3;
    printf("%d %d", new_node->x, new_node->y);
}

輸出

2 3

而在結構中，我們也可以宣告一個指向結構的指標，如下面所示

typedef struct node{
    int x;
    int y;
    struct node *node_ptr;
}Node;

node_ptr 為結構中的一個成員，是一個指標指向 node 型別。

而在 xv6 中，我們也可以看到類似的使用，-> 運算子

acquire(&kmem.lock);
r->next = kmem.freelist;
kmem.freelist = r;
release(&kmem.lock);

串列 (linked list)

上面提到我們可以在結構中宣告指向結構的指標，而我們可以試著宣告兩個node，讓其中一個 node 指向下一個 node

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int x;
    int y;
    struct node *next;
}Node;

int main(void)
{
    Node* first_node = malloc(sizeof(Node) * 1);
    first_node->x = 2;
    first_node->y = 3;
    printf("%d %d\n", first_node->x, first_node->y);

    Node* second_node = malloc(sizeof(Node) * 1);
    second_node->x = 3;
    second_node->y = 4;
    printf("%d %d", second_node->x, second_node->y);

    first_node->next = second_node;
    second_node->next = NULL;
}

輸出

2 3
3 4

上面，我們在第 22 行的地方，讓 first_node 的成員 next 指向到下一個節點，second_node 了，而像這樣一個接著一個節點，通過指標串聯起來的資料結構，我們稱為串列。

而我們可以使用一個指向結構的指標，透過指向第一個節點，來遍歷過整個串列

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int x;
    int y;
    struct node *next;
}Node;

int main(void)
{
    Node *head_node;

    Node* first_node = malloc(sizeof(Node) * 1);
    first_node->x = 2;
    first_node->y = 3;

    Node* second_node = malloc(sizeof(Node) * 1);
    second_node->x = 3;
    second_node->y = 4;

    head_node = first_node;
    first_node->next = second_node;
    second_node->next = NULL;
    
    while(head_node != NULL)
    {
        printf("%d %d\n", head_node->x, head_node->y);
        head_node = head_node->next;
    }
}

輸出

2 3
3 4

說明:
我們使用 head_node 用來走訪整個串列，只要碰到 NULL，表示已經走到串列的尾巴了，就停止走訪。


指標學習好工具 : PythonTutor


可以用來視覺化產生出指標的相關操作，輸入程式碼後，按下 Visualize Execution。


按下 next，可以逐步看到記憶體 frame 的變化

reference

你所不知道的C語言：指標篇
The C Programming Language, 2/e (Paperback)
C Programming: A Modern Approach, 2/e (Paperback)
xv6-riscv


上一篇
Day-27 C 語言, 變數範圍, volatile, inline
下一篇
Day-29 階段性小節，未完待續
系列文
與作業系統的第一類接觸 : 探索 xv6 共 31 篇
  1. 27
    Day-26 xv6 Switch Thread, yield, sched
  2. 28
    Day-27 C 語言, 變數範圍, volatile, inline
  3. 29
    Day-28 Pointer, A Pointer of A Pointer, Function Pointer
  4. 30
    Day-29 階段性小節，未完待續
  5. 31
    Day-30 Switch Thread 中 lock 的設計，sleep 和 wakeup 概念
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22207 篇
完賽人數
600 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙